package com.jhxy.algorithm.maxsubarray;

import com.jhxy.algorithm.util.PrintTool;

import java.util.StringJoiner;

/**
 * 53. 最大子数组和
 */
public class MaxSubArray {


    public int maxSubArray(int[] nums) {
        //1.如果数组长度为0，则直接返回
        if (nums.length == 0) {
            return 0;
        }

        //用maxSum存储max (sum)，防止数组全是负数
        int maxSum = getMaxNumber(nums);

        //找到那个夹逼区间
        nums = preHandle(nums);

        //用sum存储num[i,j]的和
        int sum;

        for (int i = 0; i < nums.length; i++) {
            //如果数组中只有一个元素的话
            sum = nums[i];
            if (sum > maxSum) {
                maxSum = sum;
            }

            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];
                if (sum > maxSum) {
                    maxSum = sum;
                }
            }
        }

        return maxSum;
    }

    public int getMaxNumber(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (maxSum < nums[i]) {
                maxSum = nums[i];
            }
        }
        return maxSum;
    }

    public int[] preHandle(int[] nums) {
        StringJoiner sj = new StringJoiner(",");
        //mark用于确定当前区域加和的正负性
        int mark = nums[0] >= 0 ? 1 : 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] >= 0 ? 1 : 0) == mark) {
                //如果正负性相同的话，就累加，如[1,2,3,-1],那么就把1，2，3加起来
                sum += nums[i];
            } else {
                //如果正负性不相同，如[1,2,3,-1],那么就把1，2，3加起来之后作为一个数，-1此时再作为一个数
                sj.add(String.valueOf(sum));
                sum = nums[i];
                //重置mark的值
                mark = nums[i] > 0 ? 1 : 0;
            }
        }

        //最后一次的sum也要加到sj中
        sj.add(String.valueOf(sum));
        String[] numberList = sj.toString().split(",");
        int[] newNum = new int[numberList.length];
        for (int i = 0; i < numberList.length; i++) {
            newNum[i] = Integer.parseInt(numberList[i]);
        }

        return newNum;
    }

    /**
     * 贪心算法
     */
    public int tx(int[] nums) {
        int maxNumber = Integer.MIN_VALUE;
        int sum = 0;

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (maxNumber < sum) {
                maxNumber = sum;
            }

            if (sum < 0) {
                sum = 0;
            }
        }

        return maxNumber;
    }

    /**
     * 动态规划解法
     * @param nums 原始数组
     * @return 最大子数组之和
     */
    public int dp(int[] nums) {
        int[] dp = new int[nums.length];
        //初始值没法进行对比
        dp[0] = nums[0];

        //动态规划的起始位置从1开始
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
        }

        return getMaxNumber(dp);
    }

    public static void main(String args[]) {
//        InputsForRemoveDuplicates inputs = new InputsForRemoveDuplicates("5,4,-1,7,8");
        InputsForRemoveDuplicates inputs = new InputsForRemoveDuplicates("-2,1,-3,4,-1,2,1,-5,4");
        PrintTool print = new PrintTool();
        MaxSubArray msa = new MaxSubArray();
//        System.out.println(msa.maxSubArray(inputs.nums));
//        System.out.println(msa.tx(inputs.nums));
        System.out.println(msa.dp(inputs.nums));
        print.printArray(inputs.nums);
    }
}
